#include <bits/stdc++.h>

using namespace std;

// 数字1的个数
// 给定一个整数n
// 计算所有小于等于n的非负整数中数字1出现的个数
// 测试链接 : https://leetcode.cn/problems/number-of-digit-one/

class Solution 
{
public:
    int countDigitOne(int n) 
    {
        return cnt(n, 1);
    }

    int cnt(int num, int d)
    {
        int ans = 0;
        for(long right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10)
        {
            left = tmp / 10;
            cur = tmp % 10;
            if(d == 0) --left;
            ans += left * right;
            if(cur > d) ans += right;
            else if(cur == d) ans += num % right + 1;
        }
        return ans;
    }
};


class Solution 
{
public:
    int countDigitOne(int n) 
    {
        auto s = to_string(n);
        int m = s.size(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        /*
        cnt1 表示前面填了多少个 1
    
        is_limit 表示当前是否受到了 n 的约束。若为真，则第 i 为填入的
        数字至多为 s[i]，否则可以是 9，如果在受到约束的情况下填了 s[i]，
        那么后续填入的数字仍会受到 n 的约束。
    
        isNum 表示 i 前面的数位是否填了数字。若为假，则当前位可以跳过
        （不填数字），或者要填入的数字至少为 1；若为真，则要填入的数字
        可以从 0 开始。

        对于本题来说，由于前导零对答案无影响，is_num 可以省略。
        */
        function<int(int, int, bool)> f = [&](int i, int cnt1, bool is_limit) -> int
        {
            // 找到了一个符合条件的数字
            if(i == m) return cnt1; 
            // 缓存命中
            if(!is_limit && dp[i][cnt1] != -1) return dp[i][cnt1];
            int ans = 0;
            int up = is_limit ? s[i] - '0' : 9;
            for(int d = 0; d <= up; ++d) // 枚举要填入的数字 d
            {
                ans += f(i + 1, cnt1 + (d == 1), is_limit && d == up);
            }
            if(!is_limit) dp[i][cnt1] = ans;
            return ans;
        };

        return f(0, 0, true);
    }
};